package com.kavin.collection.datastructure;

import java.util.Arrays;

/**
 * @ClassName BubbleSort
 * @Description
 * @Author kavin
 * @Date 2022/8/15 13:47
 * @Version 1.0
 */
public class BubbleSort {


    public static  void sort(int[] arr){
        for(int i = 0 ; i < arr.length ; i ++ ){
            boolean swapped = false;   //是否发生交换
            for(int j = i ; j < arr.length;j ++ ){
                if(arr[i] > arr[j]){
                    swap(arr,i,j);
                    swapped = true;
                }
                System.out.println("比较次数：" + j);
            }
            if(!swapped){
                break;
            }
            System.out.println("第" + i + "轮冒泡结果" + Arrays.toString(arr));
        }

        for (int i = 0 ; i < arr.length; i++ ){
            System.out.print(arr[i] + ",");
        }
    }



    public static void bubble(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            boolean swapped = false;   //是否发生交换
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    swapped = true;
                }
                System.out.println("比较次数：" + i);
            }
            if (!swapped) {   //说明数组有序了，不用在继续循环了
                break;
            }
            System.out.println("第" + j + "轮冒泡结果" + Arrays.toString(arr));
        }
    }



    /**
     * @return
     * @Author kavin  改造后
     * @Description 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序直接退出外层循环即可
     * @Param [arr]
     **/
    public static void bubble_v2(int[] arr) {
        int n = arr.length - 1;
        while (true) {
            int last = 0; //标识最后一次发生交换时的索引位置
            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    last = i;
                }
                System.out.println("比较次数：" + i);
            }
            n = last;
            if (n == 0) {
                break;
            }
            System.out.println("冒泡结果" + Arrays.toString(arr));
        }
    }




        /**
         * @return
         * @Author kavin
         * @Description 前后元素互换
         * @Param [arr, i, j]
         **/
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



    public static void main(String[] args) {
        int[] arr = {3,10,2,1,0,24};
        //int[] arr = {1,2,3,4,5,6};
        bubble_v2(arr);
    }
}
